// https://www.bilibili.com/video/BV1d54y1f7B3?spm_id_from=333.788.player.switch&vd_source=d6fe65f095f01f05591e89d810720ccc&p=33
// 2024-10-25

public class P038_打家劫舍1_动态规划 {

    public static void main(String[] args) {
        System.out.println(fun(new int[] {2,7,9,3,1}));
    }

    private static int fun(int[] arr) {
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0],arr[1]);

        for (int i = 2; i < dp.length; i++) dp[i] = Math.max(arr[i] + dp[i-2],dp[i-1]);
        return dp[dp.length-1];
    }

}
